\part{\'Etat de l'art}
\chapter{Discrimination de plans}
	\section{Transformation de Hough 3D}
		\subsection{Rappel : Transformée de Hough 2D}
		La transformation de Hough a vu le jour en 1959, dans le cadre de recherche sur le traitement d'images \cite{bib_Hough}. Elle a fait l'objet d'un dép\^ot de brevet durant l'année 1962 \cite{bib_Hough_brevet}. Ce procédé est utilisé pour reconnaître des éléments géométriques qui peuvent répondre à un modèle mathématique paramétrable. Les cas les plus fréquents sont ceux de la droite et du cercle. En effet, dans un plan, une droite est défini par une équation de type $y=ax+b$ ou $a$ est le coefficient directeur de la droite et $b$ son ordonnée à l'origine. De m\^eme, un cercle sera défini par l'équation $(x-a)^2+(y-b)^2=r^2$ ou le couple $(a,b)$ est le centre du cercle et $r$ son rayon. Nous allons étudier le cas simple de la droite pour démontrer cette méthode.
			\paragraph*{}
			Lorsqu'on applique la transformée de Hough, chaque ligne devient un vecteur de coordonnées paramétriques formé par :
			\begin{itemize}
			\item $\theta$ : l'angle formée entre la droite et l'axe $\vec{0x}$
			\item $p$ :  la norme du vecteur (la longueur du segment perpendiculaire à la droite d'angle $\theta$ et passant par l'origine)
			\end{itemize}
			Pour chaque pixel de l'image, on va calculer la valeur de $p$ à chaque $\theta$. Dans l'espace de Hough, les résultats donneront une sorte de sinuso\"{i}de. Lorsque chaque pixel a été traité avec chaque valeur de $\theta$, on va explorer les courbes obtenues. \' A chaque fois qu'il y a une intersection, on met le nombre de courbe qui se croisent dans un tableau servant d'accumulateur. Lorsque tout est analysé, on va rechercher les maximaux locaux dans l'accumulateur. Les paramètres reflétant ces maximaux seront ceux définissant des droites dans l'image.
La figure \ref{fig_espace_Hough} représente une droite dans un espace cartésien à deux dimensions puis dans un espace de Hough.
\begin{figure}
\centering
\includegraphics[width=10cm]{./images/espace_Hough.png}
\caption{Représentation dans un espace de Hough}
\label{fig_espace_Hough}
\end{figure}
\paragraph{}
Voici un exemple du traitement par transformée de Hough sur une image (exemple tiré de la documentation matlab). La première image sera celle de départ (fig. \ref{fig_Hough2D_1}) dans laquelle on cherche les segments les plus longs. Cette image sera tout d'abord binarisée (fig. \ref{fig_Hough2D_2}). Ensuite, on applique la transformée de Hough à chaque pixel de l'image. Le résultat de la transformée peut \^etre visualisé sur la figure \ref{fig_Hough2D_3}. Ce graphique, représente l'accumulateur des jeux de paramètres ($\theta$,$p$). Dans les zones de $-35^\circ$ et $+60^\circ$ on peut observer des points plus blancs qui sont les couples les plus représentés dans l'image. Enfin, après avoir déterminé les maximums locaux (zones les plus blanches du graphique précédent), on peut les retranscrire sur l'image initiale (fig. \ref{fig_Hough2D_4}).

\begin{figure}[h!]

\begin{minipage}{7cm}
  \centering
  \includegraphics[width=7cm]{./images/originale.png}
  \caption{Image originale}
  \label{fig_Hough2D_1}
\end{minipage}
\hfill
\begin{minipage}{7cm}
  \centering
  \includegraphics[width=7cm]{./images/binaire.png}
  \caption{Image binarisée}
  \label{fig_Hough2D_2}
\end{minipage}

\begin{minipage}{7cm}
  \centering
  \includegraphics[width=7cm]{./images/hough.png}
  \caption{Espace de Hough}
  \label{fig_Hough2D_3}
\end{minipage}
\hfill
\begin{minipage}{7cm}
  \centering
  \includegraphics[width=7cm]{./images/finale.png}
  \caption{Image finale}
  \label{fig_Hough2D_4}
\end{minipage}

\end{figure}

		\subsection{Transformée de Hough 3D, reconnaissance de plans}
		Cet algorithme peut-\^etre utilisé pour de la reconnaissance de plans dans un nuage de points (utilisation de voxels en lieu et place des pixels). Au lieu d'utiliser une équation de droite, nous utiliserons celle d'un plan (ou d'une sphère à la place des cercles).
		\paragraph{}
		Dans l'espace de Hough, un plan se traduira par l'équation suivante et ses trois paramètres :
\[ p = \cos(\theta)\sin(\phi)x+\sin(\theta)\cos(\phi)y+\sin(\phi)z \]
		\begin{itemize}
			\item $\theta$ : l'angle formé entre la droite et l'axe $\vec{0x}$
			\item $\phi$ : l'angle formé entre la droite et l'axe $\vec{0y}$
			\item $p$ :  la norme du vecteur (la longueur du segment normal au plan et passant par l'origine)
		\end{itemize}
		De la m\^eme façon que pour une droite, on explorera chaque voxel et établira tous les plans à partir de ce dernier. Ensuite, un accumulateur servira à enregistrer les résultats. Enfin, on recherchera les maximums locaux pour déduire les paramètres des plans présents. Voici un algorithme possible \cite{bib_algo_hough}:\\
\fbox{ %fbox est utilisé pour voir les bords de la minipage
\begin{minipage}[c]{17cm}
Pour chaque points pi dans l'ensemble P faire \\
|\hspace{0.5cm}	Pour chaque cellule ($\theta$,$\phi$,p) dans l'accumulateur A Faire \\
|\hspace{1cm} Si pi est dans le plan defini par ($\theta$,$\phi$,p) Alors \\
|\hspace{1.5cm} Augmenter le score de A($\theta$,$\phi$,p) de 1 \\
|\hspace{1cm} Fin Si \\
|\hspace{0.5cm}	Fin Pour \\
Fin Pour \\
Rechercher les maximums locaux dans A, qui définissent le(s) plan(s) P
\end{minipage}
}
~\\~\\
\textit{
Note : Dans le cas de l'application considérée (recherche des plans représentant les murs et le sol), il serait judicieux de réduire les angles étudiés pour la recherche de plan, afin de les cadrer avec des angles "réaliste" en ce qui concerne des murs ou le sol. Ainsi, l’exécution de l'algorithme serait plus rapide.
}

	\section{RANSAC}
	RANSAC est un acronyme signifiant RANdom SAmple Consensus. Elle a été élaboré par Fischler et Bolles en 1981 \cite{bib_RANSAC}.
	Cette approche n'est pas très éloigné de l'algorithme de la transformée de Hough en 3D.
	En effet, comme cette dernière, elle se base sur l'évaluation d'un modèle géométrique et étudie la correspondance des points vis-à-vis de ce dernier. Une fois les points correspondants au modèle obtenus, on recalcule le modèle de cet ensemble, puis on le compare au modèle \textit{parfait} théorique (équation de plan d'un sol ou d'un mur). Comme tout capteur souffre d'imprécision, l'évaluation de distance d'un point par rapport au modèle testé se fait avec une tolérance, en effet, m\^eme si le système de mesure était parfait le plan testé lui ne l'est pas forcément (mur présentant des défauts ou avec une texture particulière par exemple).
	Voici les principales étapes de ce procédé, dans le cas d'étude d'un plan (donc trois paramètres):
\fbox{ %fbox est utilisé pour voir les bords de la minipage
\begin{minipage}[c]{17cm}
|\hspace{0.0cm}	On prend au hasard trois points dans le nuage de points étudié \\
|\hspace{0.0cm} On déduit les trois paramètres du modèle selon ces trois points \\
|\hspace{0.0cm} Pour chaque point du nuage, on compare sa distance à celle du plan défini par le modèle \\
|\hspace{0.5cm} Si la distance est inférieure à un seuil $d$, on considère le point comme appartenant au plan \\
|\hspace{0.0cm}	On recalcule le modèle à partir de l'ensemble obtenu (avec méthode des moindres carrées par exemple)\\
|\hspace{0.0cm}	Si ce modèle est plus proche du modèle parfait théorique que le précédent\\
|\hspace{0.5cm}	On sauve ce nouveau modèle\\
|\hspace{0.5cm}	On sauve l'erreur obtenue \\
|\hspace{0.0cm}	Fin Si \\
|\hspace{0.0cm}	On répète cet algorithme N fois
\end{minipage}
}	
	Afin d'économiser du temps de calcul, l'algorithme peut-\^etre arrêté lorsqu'un modèle obtenu avec une erreur suffisamment faible par rapport à l'original a été obtenu. Par exemple, on peut se contenter de la recherche d'un plan horizontal pour le sol et d'un plan vertical pour les murs.
	De m\^eme, si un modèle empirique ne possède pas assez de points concordants, il peut-\^etre exclu de suite (surface trop faible ou incohérente).
	Enfin, si l'on voulait obtenir à coup sur un modèle le plus parfait, il faudrait pouvoir tester tous les triplets de point possibles du nuage initial. Pour des raisons évidentes de temps de calcul, cette manipulation n'est pas envisageable. Le nombre de tirage N doit donc \^etre évalué soit empiriquement, soit de manière formel. L'objectif  est de maximiser la probabilité $k$ ($k^3$ pour trois points) que les points sélectionnés appartiennent vraiment au plan final, le tout sous une probabilité $p$ d'avoir un plan soit correcte. On obtient alors l'équation suivante :
\[
(1-p) = (1-k^3)^N
\]
Ce qui après manipulation donne :
\[
N = \frac{log(1-p)}{log(1-k^3)}
\]
On obtient alors $N$ le nombre optimal de tirages à faire pour espérer obtenir le plan recherché vis-à-vis du modèle étudié.
	
	\section{Division - fusion}
	\subsection{\'Etape de division}
Cette méthode part du principe que l'image peut-\^etre divisée en régions possédant une caractéristique identique (par exemple les pixels sont tous de la m\^eme couleur). \'A la base de la recherche, on considère l'image tout entière comme une région (un carré dans le cas d'une image 2D ou un cube dans le cas de l'image 3D, qui sera étudiée ici). Si les voxels ne répondent pas tous à la m\^eme caractéristique, le cube étudié sera divisé en huit selon la moitié des côtés (figure \ref{fig_octree}). Ensuite, la recherche de la caractéristique se poursuivra sur les "sous-cubes" obtenues. On arr\^etera le découpage lorsque les cubes atteindront une taille minimale critique. On obtient alors des cubes remplis de points répondant à la caractéristique étudié ou alors des cubes vides.
\begin{figure}[h]
\centering
\includegraphics[width=10cm]{./images/octree.png}
\caption{Résultat des divisions successives; (a) L'image entière; (b) Première division; (c) seconde division}
\label{fig_octree}
\end{figure}
	\subsection{\'Etape de fusion}
Lorsque l'étape de division est terminé, une autre fait place afin de regrouper les cubes adjacents ayant des caractéristiques similaires	: la fusion. Durant cette procédure, chaque cube est étudié par rapport à ses 25 voisins (neuf au-dessus et au-dessous et huit autour sur le m\^eme niveau. Si la caractéristique étudié est suffisamment similaire (rose au lieu de rouge par exemple), les deux cubes sont fusionnés entre eux. L'opération est poursuivi jusqu'à ce que chacun des "sous-cube" de l'ensemble est été étudié.
	\subsection{Cas d'étude : recherche de plans}
Dans notre cas de la recherche de plans, c'est la coplanarité des voxels qui est étudiée au sein de chaque cube. Si les points d'un cube ne sont pas tous coplanaires, le cube est divisé en huit sous-cubes. Comme expliqué précédemment, à la fin de la division nous aurons un ensemble de cubes qui seront soit vides, soit possédant des points coplanaires.\\
Une fois cette étape achevée, le processus de fusion va démarrer. Afin de déterminer si deux cubes peuvent \^etre fusionné en un seul, deux critères sont pris en compte : la coplanarité et la distance. En effet, si deux plans ne sont pas coplanaires, alors on peut considérer qu'il ne forme pas le m\^eme plan (fig. \ref{fig_octree_conditions} (a) ). Cependant, ce critère seul ne suffit pas. En effet, le cas peut se présenter d'avoir deux plans coplanaires mais qui n'est rien à voir entre eux pour autant. Par exemple les marches d'un escalier. Les plans horizontaux correspondants à deux marches successives sont coplanaires. Cependant, l'information de distance entre les deux nous permet de déterminer qu'ils ne sont pas identiques (fig. \ref{fig_octree_conditions} (b) ). Ces deux plans ne peuvent donc pas \^etre fusionné.\\
La fin de cette étape nous donne des régions représentés par des cubes fusionnés entre eux. En faisant un seuillage à partir de la taille de cube, on peut déterminer lesquels sont susceptible de représenter un sol ou un mur.
\begin{figure}[h]
\centering
\includegraphics[width=10cm]{./images/octree_conditions.png}
\caption{Différents conditions de non-fusion; (a) Les plans sont adjacents mais non coplanaires; (b) Cas critique, les plans sont coplanaires, leurs cubes sont adjacents, mais ils ne peuvent pas \^etre fusionnés}
\label{fig_octree_conditions}
\end{figure}
	\section{Croissance de surface}
Cette technique est très similaire à celle utilisée pour des régions en deux dimensions. En effet, Lors d'une étude en 2D, on utilise des pixels "graines" pour faire cro\^itre des régions. En trois dimensions, ces pixels sont remplacés par des surfaces graines que l'on étendra. On retrouve notamment cette technique pour la segmentation de fa\c cades de b\^atiments (fig.\ref{fig_facade})  \cite{bib_croissance_facade} \cite{bib_croissance_Stamos}.
\begin{figure}
\centering
\includegraphics[width=10cm]{./images/facade.png}
\caption{Traitement d'un nuage de points représentant une fa\c cade par la méthode de croissance de surface \cite{bib_croissance_Stamos}}
\label{fig_facade}
\end{figure}
\paragraph*{}
Cet algorithme fonctionne en plusieurs étapes. Tout d'abord, un ensemble de n points voisins est créé pour chaque voxel. Ensuite, on détermine si cet ensemble permet de décrire un plan (si les points ne sont pas trop dispersés). Enfin, on va chercher à regrouper toutes les surfaces ainsi créées afin de parvenir à n plan plus grand contenant les plus petits initiaux. Comme pour l'étape de fusion de la méthode précédente, on considère certains critères pour déterminer si deux plans peuvent oui ou non \^etre agrégé :
\begin{itemize}
\item Le critère de co-normalité : Pour considérer que deux surfaces peuvent-\^etre réunies, on doit tout d'abord s'assurer que leurs normales ($n_1$ et $n_2$) sont orientés de la m\^eme façon. L'angle $\theta$ représentant cette orientation est calculée de la manière suivante :
\[ \theta = arcos(n_1 \times n_2) \]
Afin de prendre en compte les erreurs de mesures et le bruit durant ces dernières, cet angle sera soumis à une tolérance.
\item Le critère de distance : Comme vu dans l'algorithme précédent, deux plans peuvent \^etre coplanaire sans \^etre réuni en un seul pour autant. On pourra pour cela reprendre l'exemple des marches d'escaliers pour illustrer ce cas. Pour traiter ce critère, on étudie la distance entre les deux plans concernés.
\end{itemize}
\paragraph*{}
Comme on peut s'en douter, les graines de départ jouent un r\^ole important dans l'efficacité de l'algorithme. En effet, il est difficile de prévoir si une graine pourra ensuite s'accro\^itre convenablement. Plusieurs recherches propose des solutions à cette problématique. Par exemple, Leonardis \cite{bib_Leonardis} propose l'utilisation de plusieurs graines de départ en m\^eme temps qui vont s'accro\^itre de manière indépendante. Une autre solution consiste à recherche de manière statistique les meilleures graines de départ \cite{bib_Gotardo}.





